package airthmetic.exercise.tree.traversal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Author douhy
 * @description 二叉树遍历算法练习
 * @date 22/03/03
 */
public class TreeTraversalDemo {


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        // leetCode 144. 二叉树的前序遍历 非递归实现方式
        public static List<Integer> preOrder(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()) {
                node = stack.pop();
                list.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            }
            return list;
        }

        // leetCode 94. 二叉树的中序遍历 非递归实现方式
        public static List<Integer> inOrder(TreeNode root) {
//            List<Integer> list = new ArrayList<>();
//            if (root == null) return list;
//            TreeNode node = root;
//            Stack<TreeNode> stack = new Stack<>();
//            while (true) {
//                if (node != null){
//                    stack.push(node);
//                    node = node.left;
//                }else{
//                    if (stack.empty()) return list;
//                    node = stack.pop();
//                    list.add(node.val);
//                    node = node.right;
//                }

            // 内存消耗会更小 因为没有像第一种进了else 再次判断是否为空 少一次判断
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<>();
            while (true) {
                if (node != null) {
                    stack.push(node);
                    node = node.left;
                } else if (stack.empty()) {
                    return list;
                } else {
                    node = stack.pop();
                    list.add(node.val);
                    node = node.right;
                }
            }
        }


        // leetCode 145. 二叉树的后序遍历 非递归实现方式
        public static List<Integer> postorder(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;

            TreeNode prev = null;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode top = stack.peek();
                if (isLeaf(top) || (prev != null && isChild(top, prev))) {
                    prev = stack.pop();
                    list.add(prev.val);
                } else {
                    if (top.right != null) stack.push(top.right);
                    if (top.left != null) stack.push(top.left);
                }
            }
            return list;
        }

        protected static boolean isLeaf(TreeNode node) {
            return node.left == null && node.right == null;
        }

        protected static boolean isChild(TreeNode parent, TreeNode child) {
            return parent.left == child || parent.right == child;
        }

        // leetCode 226. 翻转二叉树 层序遍历方式
        public static TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            LinkedList<TreeNode> queue = new LinkedList();
            queue.push(root);
            while (!queue.isEmpty()){

                TreeNode node = queue.poll();

                if (node.left != null){
                    queue.push(node.left);
                }

                if (node.right != null){
                    queue.push(node.right);
                }

                TreeNode temp = node.left;
                node.left = node.right;
                node.right =  temp;

            }
            return root;
        }

    }

    public static void main(String[] args) {
        // 79,68,30,7,48,74,71,89
        TreeNode leftL = new TreeNode(7);
        TreeNode rightR = new TreeNode(48);
        TreeNode left = new TreeNode(30, leftL, rightR);

        TreeNode rightRR = new TreeNode(71);
        TreeNode right = new TreeNode(74, rightRR, null);

        TreeNode root = new TreeNode(79);
        root.right = new TreeNode(89);
        root.left = new TreeNode(68, left, right);
//
//        // 前序遍历非递归方式
//        List<Integer> preOrderList = TreeNode.preOrder(root);
//        System.out.println(preOrderList);
//        // 中序遍历非递归方式
//        List<Integer> inOrderList = TreeNode.inOrder(root);
//        System.out.println(inOrderList);

        // 后序遍历非递归方式
        List<Integer> postorderList = TreeNode.postorder(root);
        System.out.println(postorderList);


        TreeNode treeNode = TreeNode.invertTree(root);
        System.out.println(treeNode);

    }



}